package offer.offer01;

import java.util.Stack;

/**
 *
 */
public class S24反转链表 {
    //6, 100, 用一个栈装着, 也太憨了吧。
    public ListNode reverseList(ListNode head) {
        long time1 = System.currentTimeMillis();
        Stack<Integer> tmps = new Stack();
        while(head != null){
            tmps.push(head.val);
            head = head.next;
        }
        long time2 = System.currentTimeMillis();

        if(tmps.empty())
            return null;
        ListNode resultTmp = new ListNode(tmps.pop());
        ListNode result = resultTmp;
        while (!tmps.empty()){
            resultTmp.next = new ListNode(tmps.pop());
            resultTmp = resultTmp.next;
        }

        long time3 = System.currentTimeMillis();
        System.out.println((time2 - time1) + "   " + (time3 - time2));
        return result;
    }

    //在整个链表中, 用三个指针, 一个个反转
    //100, 100
    public ListNode reverseList2(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode result = head.next; //新的表头
        head.next = null;
        ListNode tmpNode = result.next; //result后面那一个, 做迭代用
        ListNode tmpNode2;
        result.next = head;
        while(tmpNode != null){
            tmpNode2 = result;
            result = tmpNode;
            tmpNode = tmpNode.next;
            result.next = tmpNode2;
        }
        return result;
    }

    // 一样, 但很酷。
    public ListNode reverseList3(ListNode head) {
        ListNode pre=null;
        ListNode temp=null;
        ListNode cur=head;
        while(cur!=null){
            temp=cur.next;
            cur.next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;
     }
}
